ЗАДАЧА 3.A. Провести анализ и составить платежные матрицы следующих игр:

Вариант 10.

Игрок А записывает одно из двух чисел: 1 или 2, игрок В — одно из трех чисел: 1, 2 или 3.Если сумма написанных чисел четная, то игрок В платит игроку А эту сумму в рублях; если она нечетная, то, наоборот, игрок А платит игроку В эту сумму.

Внимание!

Это ОЗНАКОМИТЕЛЬНАЯ ВЕРСИЯ работы №3399, цена оригинала 200 рублей. Оформлена в программе Microsoft Word.

Оплата. Контакты.

Решение:

Игра состоит из двух ходов; оба — личные. У нас (А) две стратегии: А1 — писать 1; А2 — писать 2. У противника (В)- три стратегии. Возможны следующие ситуации:

А1-В1. Оба игрока написали «1», выигрыш игрока А равен 2.

А1-В2. Игрок А написал «1», игрок В — «2». Выигрыш игрока А равен -3.

А1-В3. Игрок А написал «1», игрок В — «3». Выигрыш игрока А равен 4.

А2-В1. Игрок А написал «2», игрок В — «1». Выигрыш игрока А равен -3.

А2-В2. Игрок А написал «2», игрок В — «2». Выигрыш игрока А равен 4.

А2-В3. Игрок А написал «2», игрок В — «3». Выигрыш игрока А равен -5.

Игра представляет собой игру 23 с матрицей, приведенной в таблице:

Таблица 1. Таблица 2.

B

A B1 B2 B3 B

A B1 B2

A1 2 -3 4 A1 (0,0) (-5,5)

А2 -3 4 -5 А2 (5,-5) (-100,100)

ЗАДАЧА 3.С. Решение конечной матричной игры в смешанных стратегиях графоаналитическим методом;

Вариант 10.

Имеется игра с матрицей

В1 В2 В3 В4 В5

А1 -1 3 -2 5 1/2

А2 0 1 3 -3 2

Решение:

Проверим, прежде всего, наличие в данной игре седловых точек. Для этого вычислим нижнюю и верхнюю цены игры:

 = max min  ij = max (-2, -3) = -2,

i j

 = min max  ij = min (0, 3, 3, 5, 2) = 0

j i

и приходим к выводу:   . Следовательно, игра не имеет седловой точки и решение следует искать в области смешанных стратегий.

Построим графики функции выигрыша 1-го игрока в зависимости от вероятностей применения его чистых стратегий при различных стратегиях 2-го игрока (рис.). Стратегия В1 дает на осях I-I и II-II, соответственно, две точки с ординатами 11= -1 и 21 = 0. Соединим эти точки прямой B1. Стратегия В2 дает точки с ординатами 12 = 3, 22 = 1. Соединим прямой В2. Аналогично, строим графики стратегий В3, В4, В5.

Из графика видно, что В2 и В5 являются заведомо невыгодными стратегиями 2-го игрока.

Выделим жирной ломаной линией MLNP нижнюю границу выигрышей — минимальный выигрыш игрока А. Точка N, в которой этот минимальный выигрыш достигает наибольшего значения, определяет решение и цену игры. В точке N пересекаются стратегии В1 и В4, которые являются активными стратегиями 2-го игрока. Имея в виду теорему об активных стратегиях, составим системы уравнений.

а) для игрока А: -р1 — 0р2 = ;

5p1 — 3p2 = ;

p1 + p2 = 1.

Решаем эту систему: из (3) p1 = 1 — p2;

из (2) 5p1 — 3 + 3p1 =   8p1 — 3 = 

из (1) -p1 =  поэтому 8p1 — 3 = — p1

Отсюда p1 = 1/3; p2 = 2/3 ;  = -1/3

б) для игрока В: -q1 + 5q4 =  = -1/3;

0q1 — 3q4 =  = -1/3;

Решаем эту систему: из (2) q4 = /3 = 0,11;

из (1) q1 = 5q4 —  = 50,11 — (-0,33) = 0,89.

То есть, q1 = 8/9; q4 = 1/9;

Таким образом, оптимальными стратегиями сторон будут

Sa*= (1/3; 2/3) Sb* = (8/9; 0; 0; 1/9; 0;)

средний выигрыш  = -1/3.

ЗАДАЧА 3.В. Решение конечной игры в чистых стратегиях методом минимакса с помощью седловой точки

Для игр с приведенными платежными матрицами определить:

— нижнюю и верхнюю цены игры;

— минимаксные стратегии;

— оптимальные решения игры в чистых стратегиях с помощью седловой точки.

Вариант 10. 4 5 3 6

6 7 4 5

5 2 3 4

Запишем матрицу игры в виде таблицы:

В1 В2 В3 B4 i

A1 4 5 3 6 3

A2

6 7 5 4

A3 5 2 3 4 2

j 6 7 4 6 α = 4

β = 4

Проанализируем ситуацию.

Какую бы стратегию не выбрал игрок А, его противник В выберет такую стратегию, чтобы минимизировать свой проигрыш. Так как W2 = — W1, то игрок В, тем самым, старается минимизировать выигрыш игрока А, т.е. чтобы выигрыш игрока А был равен

Определим i для каждой стратегии игрока А.

В ответ игрок А выберет свою стратегию таким образом, чтобы в этой cитуации максимизировать свой минимальный выигрыш, т.е.

a23 = 4.

 = 4 есть нижняя цена игры, она достигается при стратегии А2, которая является максиминной стратегией игрока А.

С другой стороны, какую бы стратегию не выбрал игрок В, игрок А выберет свою такую стратегию, чтобы максимизировать свой выигрыш и, тем самым максимизировать проигрыш игрока В, т.е. .

Определим для каждой стратегии игрока В.

В ответ игрок В выберет свою стратегию таким образом, чтобы в этой ситуации минимизировать свой проигрыш, т.е.

a23 = 4.

 = 4 есть верхняя цена игры, она достигается при стратегии В3, которая является минимаксной стратегией игрока В.

В данной игре == a23 = 4, т.е. игра имеет седловую точку, в которой оба игрока получают свои гарантированные выигрыши, равные цене игры

V = =  = 4.

Стратегии А2 и В3 являются оптимальными стратегиями.

ЗАДАЧА 3.D. Приведение конечной матричной игры к задачам линейного программирования;

Для игры, заданной платежной матрицей (таблицей) :

а) убедиться в отсутствии решения в чистых стратегиях;

б) обосновать необходимость решения игры путем приведения ее к задаче ЛП;

в) сформулировать для игроков соответствующие задачи линейного программирования (составить целевые функции, системы ограничительных условий), провести анализ полученных задач ЛП на двойственность.

Вариант 10.

В1 В2 В3 В4

А1 0,8 0,2 0,4 0,2

А2 0,4 0,5 0,6 0,5

А3 0,1 0,7 0,3 0,1

А4 0,8 0,7 0,6 0,1

Решение:

Чтобы не иметь дела с дробями, умножим все элементы матрицы на 10; при этом цена игры увеличится в 10 раз, а решение не изменится. Получим матрицу:

В1 В2 В3 В4

А1 8 2 4 2

А2 4 5 6 5

А3 1 7 3 1

А4 8 7 6 1

Проверим наличие седловой точки в данной игре:

 = ij = max (2; 4; 1; 1) = 4;

 = ij = min (8; 7; 6; 5) = 5.

Видим, что , то есть, игра не имеет седловой точки, следовательно ее решение ищем в области смешанных стратегий. Так как игра имеет размерность 4х4, для решения сведем ее к задаче линейного программирования.

На основании теоремы об активных стратегиях запишем уравнения для определения оптимальной стратегии игрока А:

8•p1 + 4•p2 + p3 + 8•p4   — при В1;

2•p1 + 5•p2 + 7•p3 + 7•p4   — при В2;

4•p1 + 6•р2 + 3•p3 + 6•p4   — при В3;

2•p1 + 5•р2 + p3 + p4   — при В4;

р1 + р2 + р3 + p4 = 1.

Разделив обе части уравнений на  > 0 и обозначив Gi = pi/ , получим

8•G1 + 4•G2 + G3 + 8•G4  1;

2•G1 + 5•G2 + 7•G3 + 7•G4  1; (3.1)

4•G1 + 6•G2 + 3•G3 + 6•G4  1;

2•G1 + 5•G2 + G3 + G4  1;

G1 + G2 + G3 + G4 = 1/ ,

Решение игры должно максимизировать значение , значит, функция Ф = 1/  = G1 + G2 + G3 + G4 должна принимать минимальное значение. То есть, имеем задачу линейного программирования

найти значения переменных Gi  0, i = 1, 4, обеспечивающие минимум линейной функции Ф = 1/ = G1 + G2 + G3 + G4 при ограничениях (3.1) и условии неотрицательности переменных Gi

Для определения оптимальной стратегии игрока В составим систему уравнений: 8•q1 + 2•q2 + 4•q3 + 2•q4   — при А1;

4•q1 + 5•q2 + 6•q3 + 5•q4   — при А2;

q1 + 7•q2 + 3•q3 + q4   — при А3;

8•q1 + 7•q2 + 6•q3 + q4   — при А4;

q1 + q2 + q3 + q4 = 1.

Разделив обе части уравнений на  > 0, и обозначив Uj =1/, получим

8•U1 + 2•U2 + 4•U3 + 2•U4  1;

4•U1 + 5•U2 + 6•U3 + 5•U4  1;

U1 + 7•U2 + 3•U3 + U4  1; (3.2)

8•U1 + 7•U2 + 6•U3 + U4  1;

U1 + U2 + U3 + U4 = 1/

и учитывая, что решение игры должно минимизировать , следовательно максимизировать 1/, получим задачу линейного программирования для определения оптимальной стратегии игрока В, которая является двойственной к задаче определения оптимальной стратегии игрока А и формулируется так:

найти значения переменных Uj  0, i = 1, 4, обеспечивающие максимум линейной функции F = 1/ = U1 + U2 + U3 +U4 при ограничениях (3.2) и условии неотрицательности переменных Gi

Введя дополнительные неотрицательные переменные z1, z2, z3, z4 неравенства преобразуем в уравнения, затем решим полученную задачу линейного программирования с помощью симплексного метода.